package com.example.leetcode.solution;

import com.example.leetcode.ListNode;

import java.util.Stack;

public class Solution234 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(0, new ListNode(1)));
        new Solution234().isPalindrome(head);
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode reverseList = reverseList(head);
        while(head != null){
            if(head.val != reverseList.val){
                return false;
            }
            head = head.next;
            reverseList = reverseList.next;
        }
        return true;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode newHead = new ListNode(head.val);
        while(head.next != null){
            ListNode next = head.next;
            ListNode temp = newHead;
            newHead = new ListNode(next.val);;
            newHead.next = temp;
            head = next;
        }
        return newHead;
    }

    public boolean isPalindrome2(ListNode head) {
        if (head == null) {
            return false;
        }
        int count = count(head);
        int mid = count / 2;
        if (mid == 0) {
            return true;
        }
        if (count % 2 != 0) {
            mid++;
        }
        Stack<ListNode> stack = new Stack<>();
        int index = 1;
        boolean pass = count % 2 == 0;
        while (head != null) {
            if (index <= mid) {
                stack.push(head);
                if (pass || (!pass && index != mid)) {
                    head = head.next;
                }
                index++;
            } else {
                if (!pass) {
                    pass = true;
                } else {
                    index++;
                }
                ListNode pop = stack.pop();
                if (pop.val != head.val) {
                    return false;
                }
                head = head.next;
            }
        }
        return true;
    }

    private int count(ListNode head) {
        if (head == null) {
            return 0;
        }
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }


}
